1810G - The Maximum Prefix - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=5010;
int T,n,x,y;
int a[N],b[N],dp[N][N];
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x<y?x-y+mod:x-y;}
int mul(int x,int y){return 1ll*x*y%mod;}
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x)) if (y&1) ans=mul(ans,x);
	return ans;
}
int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		for (int i=1;i<=n;i++){
			scanf("%d%d",&x,&y);
			a[i]=mul(x,ksm(y,mod-2));
			b[i]=(1-a[i]+mod)%mod;
		}
		for (int i=0;i<=n;i++) scanf("%d",&dp[1][i]);
		for (int i=2;i<=n+1;i++)
			for (int j=0;j<=n;j++) dp[i][j]=0;
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++) dp[i+1][j-1]=add(dp[i+1][j-1],mul(dp[i][j],a[i]));
			for (int j=0;j<n;j++) dp[i+1][j+1]=add(dp[i+1][j+1],mul(dp[i][j],b[i]));
			dp[i+1][0]=add(dp[i+1][0],mul(dp[i][0],b[i]));
		}
		for (int i=2;i<=n+1;i++) printf("%d ",dp[i][0]);
		putchar('\n');
	}
}